package tree.balanced;

/**
 * https://leetcode-cn.com/problems/balanced-binary-tree/
 * 判断一颗树是否为平衡二叉树  (一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 )
 *
 * @author xushijian
 * @date 2021/08/16 12:35
 */
public class BalancedBinaryTree {

    public static void main(String[] args) {
        //[3,9,20,null,null,15,7]
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);


        System.out.println(new BalancedBinaryTree().isBalanced(root));
        //[1,2,2,3,3,null,null,4,4]
        TreeNode ret = new TreeNode(1);
        ret.left = new TreeNode(2);
        ret.right = new TreeNode(2);
        ret.left.left = new TreeNode(3);
        ret.left.right = new TreeNode(3);
        ret.left.left.left = new TreeNode(15);
        ret.left.left.right = new TreeNode(7);

        System.out.println(new BalancedBinaryTree().isBalanced(ret));
    }

    public boolean isBalanced(TreeNode root) {

        if (root == null) {
            return true;
        }

        return maxTree(root) != -1;
    }

    private int maxTree(TreeNode root) {

        if (root == null) {
            return 0;
        }
        int left = maxTree(root.left);
        int right = maxTree(root.right);
        if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        } else {
            return Math.max(left, right) + 1;
        }
    }

    //3               ---> 3
    //9 --> 1
    //20  --> 2
    //15 --> 1
    //7 --> 1
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}